/*
**	Author : Neha Agashe (0501)
**		 Ravindra Chaudhari (0504)
*/


# include<stdio.h>
# include<math.h>

# define lowerlimit -1
# define upperlimit 1
# define pi 3.1415926535
# define n 10
# define tol 0.000001

double f(double x)
{
	double rval;
	rval = 1/(1+12*pow(x,2));
	return rval;

//	return exp(x);
}

int main()
{
	double xk[n+1], tn[n+1][n+1], c[n+1];
	int i,j;

/*	printf("Enter the no of nodes...\n");
	scanf("%d",&n);
*/

	for(i=0;i<=n;i++)
	{
		double y;
		y = ((2*i+1)*pi)/(2*(n+1));
		xk[i] = cos(y);
	}

	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			if(j==0)
				tn[i][j] = 1;
			else
			if(j==1)
				tn[i][j] = xk[i];
			else
			{
				tn[i][j] = 2*xk[i]*tn[i][j-1] - tn[i][j-2];
			}
		}
	}

	for(i=0;i<=n;i++)
	{
		c[i] = 0;
		for(j=0;j<=n;j++)
		{
			c[i] = c[i] + f(xk[j])*tn[j][i];
		}
		if(i==0)
			c[i] = c[i]/(n+1);
		else
			c[i] = (2*c[i])/(n+1);
	}

/*	for(i=0;i<=n;i++)
	{
		printf("%lf\t",c[i]);
	}
*/
/*	printf("The chebyshev's polynomial is...\n");

	for(i=0;i<=n;i++)
	{
		printf("%lf * T(%d)",c[i],i);
		if(i<n)
			printf(" + ");
		else
			printf("\n");
	}
*/	
	double coeff[n+1][n+1];

/*	for(i=0;i<=n;i++)
	{
		coeff[i][i] = pow(2,i-1);
	}
*/

	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			coeff[i][j] = 0;
		}
	}

	coeff[0][0] = 1;
	coeff[1][1] = 1;

	for(i=2;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			coeff[i][j] = coeff[i][j] + 2*coeff[i-1][j-1];
		}

		for(j=0;j<=n;j++)
		{
			coeff[i][j] = coeff[i][j] - coeff[i-2][j];
		}
	}

/*	printf("The coeff matrix is...\n");

	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			printf("%lf  ",coeff[i][j]);
		}
		printf("\n");
	}
*/
	double final_coeff[n];

	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			coeff[i][j] = coeff[i][j] * c[i];
		}
	}

	for(i=0;i<=n;i++)
	{
		final_coeff[i] = 0;
		for(j=0;j<=n;j++)
		{
			final_coeff[i] = final_coeff[i] + coeff[j][i];
		}
	}

/*	printf("The final coefficients...\n");
	for(i=0;i<=n;i++)
	{
		printf("%lf \n",final_coeff[i]);
	}
*/

	FILE *fp,*fs;
	
	fp = fopen("Plot_Chebychev_graph.txt","w");
	fs = fopen("Plot_Actual_graph.txt","w");
	double h = 0.02;
	double val = -1;
	double fval;
	
	while(fabs(val-1)>=tol)
	{

		fval = 0;
		
		for(i=0;i<=n;i++)
		{
			fval = fval + pow(val,i)*final_coeff[i];
		}
		fprintf(fp,"%lf %lf\n",val,fval);
		fprintf(fs,"%lf %lf\n",val,f(val));
		val = val + h;

	}

	fclose(fp);

	return 0;
}
